package features.advance.leetcode.tree.medium;

import java.util.Stack;

/**
 *  剑指 Offer 33. 二叉搜索树的后序遍历序列
 *
 *  难度：中等
 *
 * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
 *
 *
 *
 * 参考以下这颗二叉搜索树：
 *
 *      5
 *     / \
 *    2   6
 *   / \
 *  1   3
 * 示例 1：
 *
 * 输入: [1,6,3,2,5]
 * 输出: false
 * 示例 2：
 *
 * 输入: [1,3,2,6,5]
 * 输出: true
 *
 *
 * 提示：
 *
 * 数组长度 <= 1000
 *
 * @author LIN
 * @date 2021-07-02
 */
public class Solution33 {

    public static void main(String[] args) {
        Solution solution = new Solution() {
            /**
             *  辅助单调栈
             * 设后序遍历倒序列表为 [r{n}, r{n-1},...,r1]
             * ，遍历此列表，设索引为 ii ，若为 二叉搜索树 ，则有：
             * 当节点值 r_i > r_{i+1}时： 节点 r_i
             *   一定是节点 r_{i+1}
             *   的右子节点。
             * 当节点值 r_i < r_{i+1}
             *   时： 节点 r_i
             *   一定是某节点 rootroot 的左子节点，且 rootroot 为节点 r_{i+1}, r_{i+2},..., r_{n}
             *   中值大于且最接近 r_i
             *   的节点（∵ rootroot 直接连接 左子节点 r_i）。
             * 当遍历时遇到递减节点 r_i < r_{i+1}
             *   ，若为二叉搜索树，则对于后序遍历中节点 r_i
             *   右边的任意节点 r_x 属于∈ [r_{i-1}, r_{i-2}, ..., r_1] ，必有节点值 r_x < root
             *
             * @param postorder
             * @return
             */
            @Override
            public boolean verifyPostorder(int[] postorder) {
                // 倒序
                // {6,8,9,7,3,5,1,2,0}
                Stack<Integer> stack = new Stack<>();
                int root = Integer.MAX_VALUE;
                for(int i = postorder.length - 1; i >= 0; i--) {
                    if(postorder[i] > root) {
                        return false;
                    }
                    while(!stack.isEmpty() && stack.peek() > postorder[i]){
                        root = stack.pop();
                    }
                    stack.add(postorder[i]);
                }
                return true;
            }
        };
        int[] postorder = {0,2,1,5,3,7,9,8,6}; // [6,3,8,1,5,7,9,0,2]
        boolean b = solution.verifyPostorder(postorder);
        System.out.println(b);
    }

    static class Solution {
        /**
         *  递归分治：
         *  根据二叉搜索树的定义，可以通过递归，判断所有子树的正确性（即其后序遍历是否满足二叉搜索树的定义），
         *  若所有子树都正确，则此序列为二叉搜索树的后序遍历。
         *
         *   递归解析：
         *      终止条件：当i>=j，说明此子树节点数量<=1，无需判断正确性，因此直接返回true；
         *
         *      递推工作：
         *          1、划分左右子树：遍历后序遍历的[i，j]区间元素，寻找第一个大于根节点的节点，索引记为m。此时，可划分出左子树区间[i，m-1]、
         *          右子树区间[m,j-1]、根节点索引j。
         *          2、判断是否为二叉搜索树：
         *              左子树区间[i,m-1]内的所有节点都应<postorder[j]。而第1.划分左右子树步骤已经保证左子树区间的正确性，因此只
         *              需要判断右子树区间即可。
         *              右子树区间[m,j-1]内的所有节点都应>postorder[j]，实现方式为遍历，当遇到 \leq postorder[j]≤postorder[j] 的节点则跳出；则可通过 p = jp=j 判断是否为二叉搜索树。
         *               返回值： 所有子树都需正确才可判定正确，因此使用 与逻辑符 \&\&&& 连接。
         *              1、p = j ： 判断 此树 是否正确。
         *              2、recur(i,m−1) ： 判断 此树的左子树 是否正确。
         *              3、recur(m,j−1) ： 判断 此树的右子树 是否正确。
         *
         *
         * @param postorder
         * @return
         */
        public boolean verifyPostorder(int[] postorder) {
            return recur(postorder, 0, postorder.length - 1);
        }
        boolean recur(int[] postorder, int i, int j) {
            if(i >= j) {
                return true;
            }
            int p = i;
            while(postorder[p] < postorder[j]) {
                p++;
            }
            int m = p;
            while(postorder[p] > postorder[j]) {
                p++;
            }
            return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1);
        }
    }
}
